#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//class Solution {
//public:
//    void duplicateZeros(vector<int> arr)
//    {
//        int dest = 0, cur = 0;
//        int n = arr.size() - 1;
//        while (dest <=n)
//        {
//            if (arr[cur]) dest++;
//            else
//            {
//                dest += 2;
//                if (dest > n)
//                {
//                    arr[n] = 0;
//                    dest =n-1;
//                    cur--;
//                    break;
//                }
//            }
//            cur++;
//        }
//        while (cur >= 0)
//        {
//            if (arr[cur])
//            {
//                arr[dest--] = arr[cur--];
//            }
//            else {
//                arr[dest--] = 0;
//                arr[dest--] = 0;
//                cur--;
//            }
//        }
//
//    }
//};
//int main()
//{
//    Solution s;
//    s.duplicateZeros({ 0,0,0,0,0,0,0 });
//}
//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr)
//    {
//        int dest = -1, cur = -1;
//        int n = arr.size() - 1;
//        while (dest < n)
//        {
//            cur++;
//            if (arr[cur]) dest++;
//            else
//            {
//                dest += 2;
//                if (dest > n)
//                {
//                    arr[n] = 0;
//                    dest = n - 1;
//                    cur--;
//                    break;
//                }
//            }
//        }
//        while (cur >= 0)
//        {
//            if (arr[cur])
//            {
//                arr[dest--] = arr[cur--];
//            }
//            else {
//                arr[dest--] = 0;
//                arr[dest--] = 0;
//                cur--;
//            }
//        }
//
//    }
//};
//class Solution {
//public:
//    int happynum(int n)
//    {
//        int ans = 0;
//        while (n)
//        {
//            int a = n % 10;
//            ans += a * a;
//            n /= 10;
//        }
//        return ans;
//    }
//    bool isHappy(int n)
//    {
//        int num1 = happynum(n);
//        int num2 = happynum(happynum(n));
//        while (num1 != num2)
//        {
//            num1 = happynum(num1);
//            num2 = happynum(happynum(num2));
//        }
//        return num1 == 1;
//    }
//};
//class Solution {
//public:
//    int maxArea(vector<int>& height)
//    {
//        int s = 0;
//        int left = 0, right = height.size() - 1;
//        while (left < right)
//        {
//            if (height[left] < height[right])
//            {
//                s = max(height[left] * (right - left), s);
//                left++;
//            }
//            else
//            {
//                s = max(height[right] * (right - left), s);
//                right--;
//            }
//        }
//        return s;
//    }
//};
//class Solution {
//public:
//    int triangleNumber(vector<int> nums)
//    {
//        int ans=0;
//        sort(nums.begin(), nums.end());
//        for (int n = nums.size() - 1; n >= 2; n--)
//        {
//            int left = 0, right = n - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[n]) ans += right - left, right--;
//                else left++;
//            }
//        }
//        return ans;
//    }
//};
//int main()
//{
//    Solution N;
//    N.triangleNumber({ 2,2,3,4 });
//}
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target)
//    {
//        int left = 0, right = price.size() - 1;
//        while (left < right)
//        {
//            if (price[left] + price[right] > target)
//                right--;
//            else if (price[left] + price[right] < target)
//                left++;
//            else
//                return { price[left],price[right] };
//        }
//        return { -1,-1 };
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ans;
//        int i = 0;
//        while (i < nums.size() - 2)
//        {
//            if (nums[i] > 0)
//                return ans;
//            int left = i + 1, right = nums.size() - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] + nums[i] == 0)
//                {
//                    ans.push_back({ nums[left],nums[right],nums[i] });
//                    while (left < right && nums[right] == nums[right - 1])
//                    {
//                        right--;
//                    }
//                    while (left < right && nums[left] == nums[left + 1])
//                    {
//                        left++;
//                    }
//                    right--, left++;
//                }
//                else if (nums[left] + nums[right] + nums[i] > 0)
//                {
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//            while (i < nums.size() - 2 && nums[i] == nums[i + 1])
//            {
//                i++;
//            }
//            i++;
//        }
//        return ans;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ans;
//        ans = {};
//        if (nums.size() < 4)
//        {
//            return ans;
//        }
//        int j = 0;
//        while (j < nums.size() - 3) {
//            int i = j + 1;
//            while (i < nums.size() - 2) {
//                int left = i + 1, right = nums.size() - 1;
//                while (left < right) {
//                    long long int a = 0;
//                    a += nums[left];
//                    a += nums[right];
//                    a += nums[i];
//                    a += nums[j];
//                    if (a == target) {
//                        ans.push_back({ nums[j],nums[i],nums[left], nums[right] });
//                        while (left < right && nums[right] == nums[right - 1]) {
//                            right--;
//                        }
//                        while (left < right && nums[left] == nums[left + 1]) {
//                            left++;
//                        }
//                        right--, left++;
//                    }
//                    else if (a > target) {
//                        right--;
//                    }
//                    else {
//                        left++;
//                    }
//                }
//                while (i < nums.size() - 2 && nums[i] == nums[i + 1]) {
//                    i++;
//                }
//                i++;
//            }
//            while (j < nums.size() - 3 && nums[j] == nums[j + 1]) {
//                j++;
//            }
//            j++;
//        }
//        return ans;
//    }
//};